package com.kjc.demo.basic.algorithm;

public class QuickSort {
	
	public static int[] fastSort(int[] arr,int start , int end) {
		int i = start;
		int j = end;
		int ref = arr[start];
		while(i < j) {
			
			while(i < j && arr[j] > ref) {
				j--;
			}
			
			while(i < j && arr[i] < ref) {
				i++;
			}
			if(arr[i] == arr[j] && i < j ) {
				i++; 
			}else {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				
			}
		}
		if(i-1 > start) {
			arr = fastSort(arr, start, i-1);
		}
		if(j+1 < end) {
			arr = fastSort(arr, j+1, end);
		}
		return arr;
	}
	
	/**
	 * 	快速排序
	 *  arr:需要排序的数组，begin:需要排序的区间左边界，end:需要排序的区间的右边界
	 * */
	public static int[] qsort(int arr[],int start,int end) {        
	    int pivot = arr[start];     //将区间的第一个数作为基准数   
	    int i = start; //从左到右进行查找时的“指针”，指示当前左位置       
	    int j = end;    //从右到左进行查找时的“指针”，指示当前右位置
	    //如果区间不只一个数
	    //不重复遍历
	    while (i<j) {      
	    	//当右边的数大于基准数时，略过，继续向左查找
			//不满足条件时跳出循环，此时的j对应的元素是小于基准元素的
	        while ((i<j)&&(arr[j]>pivot)) {                
	            j--;            
	        }            
	      //将右边小于等于基准元素的数填入右边相应位置
			//当左边的数小于等于基准数时，略过，继续向右查找
			//(重复的基准元素集合到左区间)
			//不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
	        while ((i<j)&&(arr[i]<pivot)) {                
	            i++;            
	        }            
	        if ((arr[i]==arr[j])&&(i<j)) {                
	            i++;            
	        } else {                
	            int temp = arr[i];                
	            arr[i] = arr[j];                
	            arr[j] = temp;            
	        }        
	    }        
	    //此时的i即为基准元素的位置
		//对基准元素的左边子区间进行相似的快速排序
	    if (i-1>start) arr=qsort(arr,start,i-1);   
	    //对基准元素的右边子区间进行相似的快速排序
	    if (j+1<end) arr=qsort(arr,j+1,end);        
	    return (arr);    
	} 
	
	//快速排序算法(从小到大)
	//arr:需要排序的数组，begin:需要排序的区间左边界，end:需要排序的区间的右边界
	public static void quickSort(int[] arr,int begin,int end)
	{
		//如果区间不只一个数
		if(begin < end)
		{
			int temp = arr[begin]; //将区间的第一个数作为基准数
			int i = begin; //从左到右进行查找时的“指针”，指示当前左位置
			int j = end; //从右到左进行查找时的“指针”，指示当前右位置
			//不重复遍历
			while(i < j)
			{
				//当右边的数大于基准数时，略过，继续向左查找
				//不满足条件时跳出循环，此时的j对应的元素是小于基准元素的
				while(i<j && arr[j] > temp) {
					j--;
					arr[i] = arr[j];
				}
				//将右边小于等于基准元素的数填入右边相应位置
				//当左边的数小于等于基准数时，略过，继续向右查找
				//(重复的基准元素集合到左区间)
				//不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
				while(i<j && arr[i] <= temp) {
					i++;
					arr[j] = arr[i];
				}
				//将左边大于基准元素的数填入左边相应位置
			}
			//将基准元素填入相应位置
			arr[i] = temp;
			//此时的i即为基准元素的位置
			//对基准元素的左边子区间进行相似的快速排序
			quickSort(arr,begin,i-1);
			//对基准元素的右边子区间进行相似的快速排序
			quickSort(arr,i+1,end);
		}
		//如果区间只有一个数，则返回
		else
			return;
	}

	
	public static void main(String[] args) {
		int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};
		int length = arr.length - 1;
		arr = qsort(arr, 0, length);
		for(int i : arr) {
			System.out.print(i + "\t");
		}
		
	}
	
}
